// https://www.lintcode.com/problem/find-median-from-data-stream/description

// 法一：每次排序 O(n^2logn)
// 法二：quick select，线性，n次 O(n^2)
// 法三：插入排序 O(n^2)
class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: the median of numbers
     */
    vector<int> medianII(vector<int> &nums) {
        priority_queue<int> maxQue;
        priority_queue<int, vector<int>, greater<int>> minQue;
        vector<int> res;
        for (int i = 0; i < nums.size(); ++i) {
            if (maxQue.empty() || nums[i] < maxQue.top()) {
                maxQue.push(nums[i]);
            } else {
                minQue.push(nums[i]);
            }
            if (minQue.size() != maxQue.size() && (minQue.size() != maxQue.size() - 1)) {
                if (minQue.size() > maxQue.size()) {
                    int tmp = minQue.top();
                    minQue.pop();
                    maxQue.push(tmp);
                } else {
                    int tmp = maxQue.top();
                    maxQue.pop();
                    minQue.push(tmp);
                }
            }
            // res.push_back(minQue.top());
            res.push_back(maxQue.top());
        }
        return res;
    }
};